package com.acwing.lc.part1;

/**
 * @author rkc
 * @date 2022/9/13 9:10
 */
public class LC41缺失的第一个正数 {

    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        if (n == 0) return 1;
        for (int i = 0; i < n; i++) {
            if (nums[i] != Integer.MIN_VALUE) {
                nums[i]--;
            }
        }
        for (int i = 0; i < n; i++) {
            while (nums[i] >= 0 && nums[i] < n && nums[i] != i && nums[i] != nums[nums[i]]) {
                int t = nums[i];
                nums[i] = nums[nums[i]];
                nums[t] = t;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i) {
                return i + 1;
            }
        }
        return n + 1;
    }
}
